Papers^γ

I'm in love with this paper! ### Non-worst-case analysis: In practice, "we are not interested in all problem instances, but only in those which can actually occur in reality." "The notion of stability [...] is a concrete way to formalize the notion that the only instances of interest are those for which small perturbation in the data (which may reflect e.g. some measurement errors) do not change the optimal partition of the graph." This Stable Analysis is different from "Smoothed Analysis" where "one shows that the hard instances form a discrete and isolated subset of the input space". ### Open problems: **Conjecture:** There exists some constant $\gamma^{*}$ such that $\gamma^{*}$-stable instances can be solved in polynomial time. **Question:** it is shown that $\gamma$-stable instances, with $\gamma>\sqrt{\Delta n}$, can be solved in polynomial time. Can this be improved (without further assumptions such as a lower bound on the minimum degree)? As $\sqrt{\Delta n}$ is usually large, this may not be useful in practice. **Question:** How does the algorithm "FindMaxCut" (page 6) perform in practice on real-world instances??? **Question:** How about the greedy heuristic?: Start from a random cut and do passes on the nodes moving each node to the other side of the cut if the size of the cut increases until convergence. Does it have some guarantee on $\gamma$-stable instances? ### Extended spectral clustering: "Let D be a diagonal matrix. Think of W + D as the weighted adjacency matrix of a graph, with loops added. Such loops do not change the weight of any cut, so that regardless of what D we choose, a cut is maximal in W iff it is maximal in W + D. Furthermore, it is not hard to see that W is $\gamma$-stable, iff W + D is. Our approach is to first find a “good” D, and then take the spectral partitioning of W + D as the maximal cut. These observations suggest the following question: Is it true that for every $\gamma$-stable instance W with γ large enough there exists a diagonal D for which extended spectral partitioning solves Max-Cut? If so, can such a D be found efficiently? Below we present certain sufficient conditions for these statements." I did not fully understand what is presented below that paragraph. Let G be a $\gamma$-stable graph, how do I get $D$? ### Goemans-Williamson algorithm: The approximation guarantee of the Goemans-Williamson algorithm is better on $\gamma$-stable instances than in general. ### Random model: With high probability, the extended specral clustering leads to the optimal cut on $\gamma$-stable instances generated from a certain random model for $\gamma\geq 1+\Omega(\sqrt{\frac{\log(n)}{n}})$. ### Typos: - page 3, Proposition 2.1: " A graph G graph" - page 4: "this follows from Definition 2.1", should be "Proposition 2.1". - page 5, Definition 2.2: should be "E" instead of "e" in the equation. - page 5: "which must to be on the" and "of the optional cut" -> "optimal". - page 8: "we multiply it be a PSD matrix"